package leetcode.code1186;

public class Solution {

	public int maximumSum(int[] arr) {
		int len = arr.length;
		if (len == 1) {
			return arr[0];
		}
		int[] l = new int[len];
		l[0] = arr[0];
		for (int i = 1; i < l.length; i++) {
			l[i] = Math.max(l[i - 1] + arr[i], arr[i]);
		}
		int[] r = new int[len];
		r[len - 1] = arr[len - 1];
		for (int i = len - 2; i >= 0; i--) {
			r[i] = Math.max(r[i + 1] + arr[i], arr[i]);
		}
		int ans = Math.max(Math.max(l[0], l[1]), Math.max(r[len - 2], r[len - 1]));
		for (int i = 1; i < r.length - 1; i++) {
			int cur1 = Math.max(Math.max(l[i], r[i]), l[i] + r[i + 1]);// i位置不删掉
			int cur2 = Math.max(Math.max(l[i - 1], r[i + 1]), l[i - 1] + r[i + 1]);// i位置删掉
			ans = Math.max(ans, Math.max(cur1, cur2));
		}
		return ans;
	}

}
